// Created by WXX on 2021/12/13 22:59
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：136 ms, 在所有 C++ 提交中击败了48.18%的用户
 * 内存消耗：39 MB, 在所有 C++ 提交中击败了82.12%的用户
 */
class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> g(n);
        for (auto &p : paths) {
            int a = p[0] - 1, b = p[1] - 1;
            g[a].push_back(b);
            g[b].push_back(a);
        }

        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            bool st[5] = {};
            for (auto j : g[i])
                st[res[j]] = true;

            for (int j = 1; j <= 4; j++)
                if (!st[j]) {
                    res[i] = j;
                    break;
                }
        }
        return res;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> paths = {
            {1, 2},
            {2, 3},
            {3, 1}
    };
    OutputBasicArray1D(Solution().gardenNoAdj(3, paths));  // [1, 2, 3]

    return 0;
}
